package problems.daily;

import utils.beans.TreeNode;

/**
 * 938. 二叉搜索树的范围和
 *
 * @author habitplus
 * @version: 1.0
 * @history: create by guan at 2024/2/26 20:51
 */
public class DT938 {
    public int rangeSumBST(TreeNode root, int low, int high) {
        return calcBSTSum(root, low, high);
    }

    private int calcBSTSum(TreeNode root, int min, int max) {
        if (root == null) {
            return 0;
        }

        // 根节点的值小于 min，则 [min, max] 可能在右子树中
        if (root.val < min) {
            return calcBSTSum(root.right, min, max);
        }

        // 根节点的值大于 max，则 [min, max] 可能在左子树中
        if (root.val > max) {
            return calcBSTSum(root.left, min, max);
        }

        // 根节点的值在 [min, max] 范围内，则左子树、右子树中可能存在 [min, max] 范围中的节点
        return root.val + calcBSTSum(root.left, min, max) + calcBSTSum(root.right, min, max);
    }
}
